'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-12 14:47:37
'''
'''
5447. 石子游戏 IV
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

 

示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
'''

'''
tips:简单dp,dp[n]表示先手能否胜利。因为最优策略，那么只要存在路径，先手拿走之后，后手称为先手，这个后先手必输
即可。那么转移方程就有了，代码如下：
'''
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        import math
        dp = [False]*n
        for i in range(1, n+1):
            if int(math.sqrt(i))**2 == i:
                dp[i-1] = True
                # print(dp)
                
            else:
                for j in range(1, int(math.sqrt(i))+1):
                    dp[i-1] = dp[i-1] or not dp[i-1-j**2]
        # print(dp)
        return dp[-1]
if __name__ == "__main__":
    solution = Solution()
    n = 4
    print(solution.winnerSquareGame(n))